package wangy.pvpr.test;

import java.util.Random;
import java.util.Stack;
import java.util.Vector;

class Graph
{
	private final int vertices = 20;  //set the max number of the vertices
	private Vertex verticesList[];    
	private int adjMatrix[][];       // adjacency matrix
	private int nVertices;              // current number of vertices
	private Stack<Integer> stack;     
	private static Vector<String> vect=new Vector<String>();


	public Graph()       //constructor
	{  
		verticesList = new Vertex[vertices];
		adjMatrix = new int [vertices][vertices];
		nVertices = 0;

		for (int i=0; i<vertices; i++)
			for (int j=0; j<vertices; j++)
				adjMatrix[i][j] = 0;

		stack = new Stack<Integer>();        
	}


	public void addVertex (String label)
	{
		verticesList[nVertices++]= new Vertex(label);
	}

	public void addEdge (int start, int end)
	{
		adjMatrix[start][end] = 1;
		adjMatrix[end][start] = 1;
	}


	public void dfs()
	{  
		verticesList[0].wasVisited = true;  //set the first vertices is visited
		stack.push(0);
		vect.add("A");

		while(!stack.isEmpty())
		{  

			int n = RamGetAdjUnvisitedVertex(stack.peek());
			//call the method of getting the adjacent vertex randomly


			if (n==-1)
				stack.pop();
			//when there is no unvisited adjacent vertex 
			//pop the vertex out of the stack


			else
			{
				verticesList[n].wasVisited = true;//mark the vertex to be visited
				vect.add(verticesList[n].verticesLabel);//store the path 
				stack.push(n);

				if (verticesList[14].wasVisited == true)
				{
					while(!stack.isEmpty())
						stack.pop();
				}//empty the stack when reach the goal
			}         
		}

		for (int j=0; j<nVertices; j++)
			verticesList[j].wasVisited = false;  
	}


	public int RamGetAdjUnvisitedVertex(int n)
	{
		Vector<Integer> tempv = new Vector<Integer>();
		Random rand = new Random();

		for (int j=0; j<nVertices; j++)
		{
			if (adjMatrix[n][j] == 1 && verticesList[j].wasVisited == false)
			{
				tempv.add(j);   
				//store all the unvisited and adjacent vertices of the current one               
			}       
		} 



		if (tempv.size() >= 1)
		{ 
			int m = rand.nextInt(tempv.size());
			String a = (tempv.elementAt(m)).toString();	        int j = Integer.parseInt(a);
			return j;
		}//get a random unvisited and adjacent vertex  

		else
			return -1; 
		//when there is no unvisited and adjacent vertex
	}


	public static Vector<String> get_Vector()
	{
		return vect;
	}
	//this method will be called in the actionPerformed 
	//method of the start button which returns the path
}

